package leetcode.tree.binary.traversal;

import leetcode.tree.binary.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 101. 对称二叉树
 *
 * 判断一棵二叉树是否轴对称
 *
 */
public class SymmetricTree {

    public static void main(String[] args) {
        SymmetricTree solution = new SymmetricTree();
        TreeNode tree = solution.createTree();

        boolean res = solution.isSymmetric(tree);
        System.out.println(res);
    }

    /**
     * 创建树  [1,2,2,null,3,null,3]
     *
     * @return
     */
    public TreeNode createTree() {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(3);
        root.left = node1;
        root.right = node2;
        node1.right = node3;
        node2.right = node4;
        return root;
    }

    /**
     * 层次遍历 自己写的 太垃圾了
     *
     * @param root 树
     * @return  是否是对称树
     */
    public boolean isSymmetric0(TreeNode root) {
        if (root == null) {
            return false;
        }

        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            String[] arr = new String[len];
            // 同一层的节点都取出来
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                // 左右子节点入栈
                if (node != null) {
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
                arr[i] = node == null ? "" : node.val + "";
            }
            if (len == 1) {
                continue;
            }
            boolean res = isSymmetricArr(arr);
            if (!res) {
                return false;
            }
        }
        return true;
    }

    public boolean isSymmetricArr(String[] arr) {
        int len = arr.length;
        for (int i = 0; i < len / 2; i++) {
            if (!arr[i].equals(arr[len - 1 - i])) {
                return false;
            }
        }
        return true;
    }


    /**
     * 递归判断 对称二叉树
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return root == null || check(root.left, root.right);
    }


    /**
     * 检查两个树是否互为镜像 (互相对称)
     *
     * 递归过程
     *      判断两个指针当前节点值是否相等
     *      判断 A 的左子树与 B 的右子树是否对称
     *      判断 A 的右子树与 B 的左子树是否对称
     *
     * @param p 树1
     * @param q 树2
     * @return
     */
    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }


    /**
     * 迭代实现
     *
     * @param root  树
     * @return
     */
    public boolean isSymmetric1(TreeNode root) {
        if(root == null) {
            return true;
        }

        TreeNode u = root.left;
        TreeNode v = root.right;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            // 每次从队列中取出两个节点进行比较
            // 理论上他们也要求是对称的
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }

            // 把左节点的左子树和右节点的右子树一起入队, 这两个是互为对称的子树
            q.offer(u.left);
            q.offer(v.right);

            // 把左节点的右子树和右节点的左子树一起入队, 这两个是互为对称的子树
            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}
